Diagonals [B]

Memory limit: 256 MB

We are given a regular polygon with vertices. Let's choose of its diagonals. We would like to know if there is such a pair of diagonals that intersect (having a common end-point does not count as intersection).

Task

Write a program which:

• reads a description of the polygon and selected diagonals from the standard input,
• checks whether there is a pair of diagonals that intersect,
• writes the result to the standard output.

Input

In the first line of the input there are two integers and (, ), separated with a single space and representing the number of vertices of the polygon and the number of selected diagonals. Following lines contain descriptions of diagonals. Each line contains two integers and (), separated with a single space and representing diagonal, which joins vertex number with vertex number (polygon's vertices are numbered with natural numbers from to in a counter-clockwise manner). You can assume that each pair of numbers defining a single diagonal defines a valid diagonal (not a single vertex or polygon's edge). All diagonals in the input will be different.

Output

The first and only line of the output should contain:

• one word NIE (i.e. no in Polish), if there is no pair of diagonals that intersect, or
• two different integers and (, ), separated with a single space and representing numbers of diagonals that intersect. In case of multiple correct answers, your program can output any one of them. Diagonals are numbered in order of occurrence in the input.

Example

For the input data:

6 4
3 6
1 4
6 2
2 5

the correct result is:

2 3

and for the input data:

6 2
1 3
1 5

the correct result is:

NIE

In the image above, solid lines represent diagonals from the first input, while stroked lines represent diagonals from the second input.

Task author: Jakub Radoszewski.